package sort;

/**
 * 归并排序
 * @author zhm
 * @date 2020/10/12
 */
public class MergeSort {

    public static void sort(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }

        mergeSortInternally(arr,0,arr.length-1);
    }

    private static void mergeSortInternally(int[] a, int p, int r){
         if(p>=r){
             return;
         }
         //取数组中心位置作为分割，这里不用 （p+r）/2 的目的是防止 p+r 溢出
         int q = p+(r-p)/2;
         mergeSortInternally(a,p,q);
         mergeSortInternally(a,q+1,r);
         merge(a,p,q,r);
    }

    private static void merge(int[] a, int p, int q, int r){
        int[] temp = new int[r-p+1];
        int k = 0;
        int i = p;
        int j = q+1;
        while (i<=q && j<=r){
            if(a[i]<=a[j]){
                temp[k++] = a[i++];
            }else {
                temp[k++] = a[j++];
            }
        }
        int start = i;
        int end = q;
        if(j<=r){
            start = j;
            end = r;
        }
        while (start<=end){
            temp[k++] = a[start++];
        }

        for (int m = 0; m < temp.length; m++) {
            a[p+m] = temp[m];
        }

    }

}
